package com.wangp.mywrite.s_algorithm.dynamic_programming;

/**
 * @Author wangp
 * @Date 2020/6/5
 * @Version 1.0
 * <p>
 * <p>
 * 动态规划：
 * 求最优解的常用策略
 * 使用套路：
 * 1.暴力破解
 * 2.记忆化搜索
 * 3.递推
 */
public class Main {
    /**
     * 动态规划常规步骤
     * 1.定义状态
     *      定义 dp[i]的含义
     * 2.设置初始状态（边界）
     *      设置dp[0]的值
     * 3.确定状态转移方程
     *      比如确定dp[i]与dp[i+1]的关系
     */


    /**
     * 维基百科：
     * 1.将复杂的问题拆解成子问题
     * 2.每个子问题仅仅解决一次，并保存他们的解
     * 3.最后推导出原问题的解
     */

    /**
     * 能用动态规划的问题，通常具有以下两个特点
     * 1. 最优子结构：通过求解子问题的最优解，获得原问题的最优解
     * 2. 无后效性
     *      a.某阶段的状态一旦确定，则伺候过程的演变不再受此前各状态及决策的影响（未来与过去无关）
     *      b.在推导后面阶段的状态时，只关心前面阶段的具体状态值，不关心这个状态是怎么一步步推导出来的
     *
     *      无后效性例：
     *      //从起点（0,0）到终点（4,4)有多少种走法，只能往右或往下走
     *          1) dp(0,0) = 1
     *          2) dp(i,0) = dp(0,j) = 1
     *          3) dp(i,j) = dp(i,j-1) + dp(i-1,j)
     *          推导dp(i,j)只用到 dp(i,j-1),dp(i-1,j)的值
     *          不需要关心 dp(i,j-1),dp(i-1,j) 怎么来的
     *      有后效性：
     *      //从起点（0,0）到终点（4,4)有多少种走法，可以向左，向右，向上，向下走，并且同一个格子不能走2次
     */
    //例1 ： 零钱转换问题
    //例2 :  最大连续子序列和
    /**     给定一个长度为n的整数序列 求它的最大连续子序列和
     *      比如 -2 1 -3 4 -1 2 1 -5 4 最大连续子序列和是  4 + （-1） + 2 +1 = 6
     *
     *      状态定义:
     *      假设dp(i)是以nums[i]结尾的最大连续子序列和 (nums是整个序列)
     *      以nums[0] -2结尾的最大连续子序列是-2,所以dp(0)=-2
     *      以nums[1] 1结尾的最大连续子序列是1,所以dp(1)
     *      以nums[2] -3结尾的最大连续子序列是1、-3,所以dp(2)=dp(1)+(-3)=-2
     *      以nums[3] 4结尾的最大连续子序列是4,所以dp(3)=4
     *      以nums[4] -1结尾的最大连续子序列是4、-1,所以dp(4)=dp(3)+(-1)=3
     *      以nums[5] 2结尾的最大连续子序列是42,所以dp(5)=dp(4)+2=5
     *      以nums[6] 1结尾的最大连续子序列是4、-1、2、1,所以dp(6)=dp(5)+1=6
     *      以nums[7] -5结尾的最大连续子序列是4、-1、2、1、-5,所以dp(7)=dp(6)+(-5)=1
     *      以nums[8] 4结尾的最大连续子序列是4、-1、2、1、-5、4,所以dp(8)=dp(7)+4=5
     *
     *      dp[i] = Math.max(dp[i-1] + nums[i] , nums[i])
     */

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3};
        int cur = arr[2];
        System.out.println(cur);
        arr[2] = 4;
        System.out.println(cur);
        Person p = new Person();
        Person other = p;
        p.age = 2;
        System.out.println(other.age);
        p.age = 3;
        System.out.println(other.age);
    }

    static class Person{
        Integer age;
    }
}
